#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <unistd.h>

#include "mymem.h"
#include "testrunner.h"


#define size(array) (sizeof(array)/sizeof(array[0]))

#define USE_REALTIME_CLOCK (0)
// rt clocks requires linking with -lrt option

typedef enum strategies_enum
{
	Best = 0,
	Worst = 1,
	First = 2,
	Next = 3
} strategies;

static char strategy_names[][6]={"best","worst","first","next"};

static int is_strategy_name(char*name) {
	int i;
	for(i =0;i<size(strategy_names);i++)
		if(name && !strcmp(name,strategy_names[i] )) return 1;
	return 0;
}
static int use_strategy(char*current, char*param) {
	if(is_strategy_name(param))
		return 0==strcmp(param,current);

	if(param && strcmp(param,"all")) {
		fprintf(stderr,"%s is not a placement strategy or 'all'\n", param);
		exit(1);
	}
	return 1; // use all
}

/* performs a randomized test:
	totalSize == the total size of the memory pool, as passed to initmem2
		totalSize must be less than 10,000 * minBlockSize
	fillRatio == when the allocated memory is >= fillRatio * totalSize, a block is freed;
		otherwise, a new block is allocated.
		If a block cannot be allocated, this is tallied and a random block is freed immediately thereafter in the next iteration
	minBlockSize, maxBlockSize == size for allocated blocks is picked uniformly at random between these two numbers, inclusive
	*/
void do_randomized_test(char* strategy_filter, int totalSize, float fillRatio, int minBlockSize, int maxBlockSize, int iterations)
{
	int pointers[10000];
	int storedPointers = 0;
	int strategy;
	int smallBlockSize = maxBlockSize/10;

	FILE *log;
	log = fopen("tests.log","a");
	if(log == NULL) {
	  perror("Can't append to log file.\n");
	  return;
	}

	fprintf(log,"Running randomized tests: pool size == %d, fill ratio == %f, block size is from %d to %d, %d iterations\n",totalSize,fillRatio,minBlockSize,maxBlockSize,iterations);

	fclose(log);

	for (strategy = 0; strategy < size(strategy_names); strategy++)
	{
		if(!use_strategy(strategy_names[strategy], strategy_filter)) continue;
		mymalloc_fp mymalloc = to_malloc_implementation( strategy_names[strategy] );
		
		double sum_largest_free = 0;
		double sum_hole_size = 0;
		double sum_allocated = 0;
		int failed_allocations = 0;
		double sum_small = 0;
#if USE_REALTIME_CLOCK				
		struct timespec execstart, execend;
#else
		clock_t execstart, execend;
#endif
		int force_free = 0;
		int i;
		storedPointers = 0;

		initmem(totalSize);
#if USE_REALTIME_CLOCK		
		clock_gettime(CLOCK_REALTIME, &execstart);
#else
		execstart = clock ();
#endif
		for (i = 0; i < iterations; i++)
		{
			if ( (i % 10000)==0 )
				srand ( time(NULL) );
			if (!force_free && (mem_bytes_free() > (totalSize * (1-fillRatio))))
			{
				int newBlockSize = (rand()%(maxBlockSize-minBlockSize+1))+minBlockSize;
				/* allocate */
				int pointer = mymalloc(newBlockSize);
				if (pointer != -1)
					pointers[storedPointers++] = pointer;
				else
				{ 
					failed_allocations++;
					force_free = 1;
				}
			}
			else
			{
				int chosen;
				int pointer;

				/* free */
				force_free = 0;

				if (storedPointers == 0)
					continue;

				chosen = rand() % storedPointers;
				pointer = pointers[chosen];
				pointers[chosen] = pointers[storedPointers-1];

				storedPointers--;

				myfree(pointer);
			}

			sum_largest_free += mem_bytes_largest_hole();
			sum_hole_size += (mem_bytes_free() / mem_count_holes());
			sum_allocated += mem_bytes_allocated();
			sum_small += mem_count_small_holes(smallBlockSize);
		}
#if USE_REALTIME_CLOCK		
		clock_gettime(CLOCK_REALTIME, &execend);
#else
		execend = clock ();
#endif
		log = fopen("tests.log","a");
		if(log == NULL) {
		  perror("Can't append to log file.\n");
		  return;
		}
		
		fprintf(log,"\t=== %s ===\n",strategy_names[strategy]);
#if USE_REALTIME_CLOCK		
		fprintf(log,"\tTest took %.2fms.\n", (execend.tv_sec - execstart.tv_sec) * 1000 + (execend.tv_nsec - execstart.tv_nsec) / 1000000.0);
#else
		fprintf(log,"\tTest took %.2fms.\n", ((execend - execstart) * 1000.)/ CLOCKS_PER_SEC );
#endif
		fprintf(log,"\tAverage hole size: %f\n",sum_hole_size/iterations);
		fprintf(log,"\tAverage largest free block: %f\n",sum_largest_free/iterations);
		fprintf(log,"\tAverage allocated bytes: %f\n",sum_allocated/iterations);
		fprintf(log,"\tAverage number of small blocks: %f\n",sum_small/iterations);
		fprintf(log,"\tFailed allocations: %d\n",failed_allocations);
		fclose(log);


	}
}

/* run randomized tests against the various strategies with various parameters */
int do_stress_tests(int argc, char **argv)
{
	char* strategy = argv[1];

	unlink("tests.log");  // We want a new log file

	do_randomized_test(strategy,10000,0.25,1,1000,10000);
	do_randomized_test(strategy,10000,0.25,1,2000,10000);
	do_randomized_test(strategy,10000,0.25,1000,2000,10000);
	do_randomized_test(strategy,10000,0.25,1,3000,10000);
	do_randomized_test(strategy,10000,0.25,1,4000,10000); 
	do_randomized_test(strategy,10000,0.25,1,5000,10000);

	do_randomized_test(strategy,10000,0.5,1,1000,10000);
	do_randomized_test(strategy,10000,0.5,1,2000,10000);
	do_randomized_test(strategy,10000,0.5,1000,2000,10000);
	do_randomized_test(strategy,10000,0.5,1,3000,10000); 
	do_randomized_test(strategy,10000,0.5,1,4000,10000);
	do_randomized_test(strategy,10000,0.5,1,5000,10000);

	do_randomized_test(strategy,10000,0.5,1000,1000,10000); /* watch what happens with this test!...why? */

	do_randomized_test(strategy,10000,0.75,1,1000,10000);
	do_randomized_test(strategy,10000,0.75,500,1000,10000);
	do_randomized_test(strategy,10000,0.75,1,2000,10000); 

	do_randomized_test(strategy,10000,0.9,1,500,10000); 

	return 0; /* you nominally pass for surviving without segfaulting */
}

/* basic sequential allocation of single byte blocks */
int test_alloc_1(int argc, char **argv) {
	char *strategy_filter = argv[1];
	int strategy;


	for (strategy = 0; strategy < size(strategy_names); strategy++)
	{
		if(!use_strategy(strategy_names[strategy], strategy_filter)) continue;
		mymalloc_fp mymalloc = to_malloc_implementation(  strategy_names[strategy]  );

		int correct_holes = 0;
		int correct_alloc = 100;
		int correct_largest_free = 0;
		int i;

		int lastPointer = -1;
		initmem(100);
		for (i = 0; i < 100; i++)
		{
			int pointer = mymalloc(1);
			if ( i > 0 && pointer != (lastPointer+1) )
			{
				printf("Allocation with %s was not sequential at %i; expected %d, actual %d\n", strategy_names[strategy], i,lastPointer+1,pointer);
				return 1;
			}
			lastPointer = pointer;
		}

		if (mem_count_holes() != correct_holes)
		{
			printf("Holes not counted as %d with %s\n", correct_holes, strategy_names[strategy]);
			return	1;
		}

		if (mem_bytes_allocated() != correct_alloc)
		{
			printf("Allocated memory not reported as %d with %s\n", correct_alloc, strategy_names[strategy]);
			return	1;
		}

		if (mem_bytes_largest_hole() != correct_largest_free)
		{
			printf("Largest memory block free not reported as %d with %s\n", correct_largest_free, strategy_names[strategy]);
			return	1;
		}

	}

	return 0;
}


/* alloc, alloc, free, alloc */
int test_alloc_2(int argc, char **argv) {
	char *strategy_filter = argv[1];
	int strategy;

	for (strategy = 0; strategy < size(strategy_names); strategy++)
	{
		if(!use_strategy(strategy_names[strategy], strategy_filter)) continue;
		mymalloc_fp mymalloc = to_malloc_implementation(  strategy_names[strategy]  );
	
		int correct_holes;
		int correct_alloc;
		int correct_largest_free;
		int correct_small;
		int first;
		int second;
		int third;
		int correctThird;

		initmem(100);

		first = mymalloc(10);
		second = mymalloc(1);
		myfree(first);
		third = mymalloc(1);

		if (second != (first+10))
		{
			printf("Second allocation failed; allocated at incorrect offset with strategy %s", strategy_names[strategy]);
			return 1;
		}

		correct_alloc = 2;
		correct_small = (strategy == First || strategy == Best);

		switch (strategy)
		{
			case Best:
				correctThird = (third == first);
				correct_holes = 2;
				correct_largest_free = 89;
				break;
			case Worst:
				correctThird = (third == second+1);
				correct_holes = 2;
				correct_largest_free = 88;
				break;
			case First:
				correctThird = (third == first);
				correct_holes = 2;
				correct_largest_free = 89;
				break;
			case Next:
				correctThird = (third == second+1);
				correct_holes = 2;
				correct_largest_free = 88;
				break;
		}

		if (!correctThird)
		{
			printf("Third allocation failed; allocated at incorrect offset with %s", strategy_names[strategy]);
			return 1;
		}

		if (mem_count_holes() != correct_holes)
		{
			printf("Holes counted as %d, should be %d with %s\n", mem_count_holes(), correct_holes, strategy_names[strategy]);
			return	1;
		}

		if (mem_count_small_holes(9) != correct_small)
		{
			printf("Small holes counted as %d, should be %d with %s\n", mem_count_small_holes(9), correct_small, strategy_names[strategy]);
			return	1;
		}

		if (mem_bytes_allocated() != correct_alloc)
		{
			printf("Memory reported as %d, should be %d with %s\n", mem_bytes_allocated(0), correct_alloc, strategy_names[strategy]);
			return	1;
		}

		if (mem_bytes_largest_hole() != correct_largest_free)
		{
			printf("Largest memory block free reported as %d, should be %d with %s\n", mem_bytes_largest_hole(), correct_largest_free, strategy_names[strategy]);
			return	1;
		}

	}

	return 0;
}


/* basic sequential allocation followed by 50 frees */
int test_alloc_3(int argc, char **argv) {
	char *strategy_filter = argv[1];
	int strategy;

	for (strategy = 0; strategy < size(strategy_names); strategy++)
	{
		if(!use_strategy(strategy_names[strategy], strategy_filter)) continue;
		mymalloc_fp mymalloc = to_malloc_implementation( strategy_names[strategy] );

		int correct_holes = 50;
		int correct_alloc = 50;
		int correct_largest_free = 1;
		int i;

		int lastPointer = -1;
		initmem(100);
		for (i = 0; i < 100; i++)
		{
			int pointer = mymalloc(1);
			if ( i > 0 && pointer != (lastPointer+1) )
			{
				printf("Allocation with %s was not sequential at %i; expected %d, actual %d\n", strategy_names[strategy], i,lastPointer+1,pointer);
				return 1;
			}
			lastPointer = pointer;
		}

		for (i = 1; i < 100; i+= 2)
		{
			myfree(i);
		}

		if (mem_count_holes() != correct_holes)
		{
			printf("Holes not counted as %d with %s\n", correct_holes, strategy_names[strategy]);
			return	1;
		}
		if (mem_bytes_allocated() != correct_alloc)
		{
			printf("Memory not reported as %d with %s\n", correct_alloc, strategy_names[strategy]);
			return	1;
		}
		if (mem_bytes_largest_hole() != correct_largest_free)
		{
			printf("Largest memory block free not reported as %d with %s\n", correct_largest_free, strategy_names[strategy]);
			return	1;
		}

		for(i=0;i<100;i++) {
		  if(mem_is_allocated(i) == i%2) {
		    printf("Byte %d in memory claims to ",i);
		    if(i%2)
		      printf("not ");
		    printf("be allocated.  It should ");
		    if(!i%2)
		      printf("not ");
		    printf("be allocated.\n");
		    return 1;
		  }
		}
	}

	return 0;
}


/* basic sequential allocation followed by 50 frees, then another 50 allocs */
int test_alloc_4(int argc, char **argv) {
	char *strategy_filter = argv[1];
	int strategy;

	for (strategy = 0; strategy < size(strategy_names); strategy++)
	{
		if(!use_strategy(strategy_names[strategy], strategy_filter)) continue;
		mymalloc_fp mymalloc = to_malloc_implementation( strategy_names[strategy] );

		int correct_holes = 0;
		int correct_alloc = 100;
		int correct_largest_free = 0;
		int i;

		int lastPointer = -1;
		initmem(100);
		for (i = 0; i < 100; i++)
		{
			int pointer = mymalloc(1);
			if ( i > 0 && pointer != (lastPointer+1) )
			{
				printf("Allocation with %s was not sequential at %i; expected %i, actual %i\n", strategy_names[strategy], i,lastPointer+1,pointer);
				return 1;
			}
			lastPointer = pointer;
		}

		for (i = 1; i < 100; i+= 2)
		{
			myfree(i);
		}

		for (i = 1; i < 100; i+=2)
		{
			int pointer = mymalloc(1);
			if ( i > 1 && pointer != (lastPointer+2) )
			{
				printf("Second allocation with %s was not sequential at %i; expected %i, actual %i\n", strategy_names[strategy], i,lastPointer+1,pointer);
				return 1;
			}
			lastPointer = pointer;
		}

		if (mem_count_holes() != correct_holes)
		{
			printf("Holes not counted as %d with %s\n", correct_holes, strategy_names[strategy]);
			return	1;
		}

		if (mem_bytes_allocated() != correct_alloc)
		{
			printf("Memory not reported as %d with %s\n", correct_alloc, strategy_names[strategy]);
			return	1;
		}

		if (mem_bytes_largest_hole() != correct_largest_free)
		{
			printf("Largest memory block free not reported as %d with %s\n", correct_largest_free, strategy_names[strategy]);
			return	1;
		}

	}

	return 0;
}

int main(int argc, char **argv)
{
	set_testrunner_default_timeout(20);
	/* Tests can be invoked by matching their name or their suite name or 'all'*/
	testentry_t tests[] = {
		{"alloc1","suite1",test_alloc_1},
		{"alloc2","suite2",test_alloc_2},
		{"alloc3","suite1",test_alloc_3},
		{"alloc4","suite2",test_alloc_4},
		{"stress","suite3",do_stress_tests},
	};

 	return run_testrunner(argc,argv,tests,sizeof(tests)/sizeof(testentry_t));
}
